//
//  Graph.cpp
//  图的广度优先
//
//  Created by 刘晨 on 2018/11/26.
//  Copyright © 2018 刘晨. All rights reserved.
//

#include "Graph.hpp"
#include "Cqueue.hpp"
#include <iostream>
using namespace std;
int Graph::locate(dataType data){
    for (int i  = 0; i<vertexNum;i++) {
        if(vertex[i].data == data){
            return i;
        }
    }
    return -1;
}
void Graph::create(){
    cout<<"input Graph data\n";
    for (int i = 0; i<vertexNum; i++) {
        cin>>vertex[i].data;
        vertex[i].isAccess  = false;
    }
    for (int j = 0; j<edgeNum; j++) {
        
    cout<<"input start and end of edge:\n";
    char start ,end;
    cin>>start>>end;
    int startPosition = locate(start);
    int endPosition = locate(end);
    edge[startPosition][endPosition] = 1;
    edge[endPosition][startPosition] = 1;
        
    }
    
}
void Graph::init(int vertex, int edgeNum){
    this->vertexNum = vertex;
    this->edgeNum = edgeNum;
    for (int i = 0; i<VERTEXNUM; i++) {
        for (int j = 0; j<VERTEXNUM; j++) {
            edge[i][j] = INT_MAX;
        }
    }
    
}
void Graph::printGraph(){
    cout<<endl;
    cout<<endl;
    cout<<"顶点边:\n";
    cout<<"vertexNum:"<<vertexNum<<" edgeNum:"<<edgeNum<<endl;
    for (int i = 0; i<vertexNum; i++) {
        cout<<vertex[i].data<<"\t";
    }
    
    cout<<"边表如下：\n";
    for (int j = 0; j<edgeNum; j++) {
        for (int k = 0; k<edgeNum ; k++) {
            cout<<edge[j][k]<<"\t";
        }
        cout<<endl;
    }
}
bool  Graph::isHaveNevEdge( dataType data ){
    int position = locate(data);
    for (int i = 0; i<vertexNum; i++) {
        if(edge[position][i] !=  INT_MAX){
            return true;
        }
    }
    return false;
}
void Graph::move(dataType data){
    int positon = locate(data);
    for (int i = positon; i<vertexNum; i++) {
        vertex[i].data = vertex[i+1].data;
        vertex[i].isAccess = vertex[i+1].isAccess;
    }
    vertexNum --;
    
    for (int i = positon; i<vertexNum; i++) {
        for (int j = 0; j<vertexNum; j++) {
            edge[i][j] = edge[i+1][j];
        }
    }
    edgeNum--;
}
void Graph::addEdge(char start, char end){
    int startPositon = locate(start);
    int endPosition = locate(end);
    if(startPositon == -1 && endPosition != -1){
        vertex[vertexNum].data = start;
        vertex[vertexNum].isAccess = false;
        this->vertexNum+=1;
        this->edgeNum+=1;
        startPositon = vertexNum-1;
    }
    if(startPositon != -1 && endPosition == -1){
        vertex[vertexNum].data = end;
        vertex[vertexNum].isAccess = false;
        this->vertexNum+=1;
        this->edgeNum+=1;
        endPosition = vertexNum-1;
    }
    if(startPositon == -1 && endPosition == -1){
        vertex[vertexNum].data = start;
        vertex[vertexNum].isAccess = false;
        this->vertexNum+=1;
        this->edgeNum+=0;
        startPositon = vertexNum-1;
        
        vertex[vertexNum].data = end;
        vertex[vertexNum].isAccess = false;
        this->vertexNum+=1;
        this->edgeNum+=1;
        endPosition = vertexNum-1;
    }
    
    edge[startPositon][endPosition] = 1;
    edge[endPosition][startPositon] = 1;
    cout<<startPositon<<endPosition;
    cout<<  edge[startPositon][endPosition]<<";"<<edge[endPosition][startPositon] <<endl;
}
void Graph::deleteEdege(dataType start, dataType end){
    int startPosition = locate(start);
    int endPosition = locate(end);
    if(startPosition == -1 || endPosition == -1){
        cout<<"error\n";
        return;
    }
    edge[startPosition][endPosition] = INT_MAX;
    edge[endPosition][startPosition] = INT_MAX;
    if(! isHaveNevEdge(start)){
        move(start);
    }
    if(! isHaveNevEdge(end)){
        move(end);
    }
}
int  Graph::getFirstVertex(dataType data){
    int position = locate(data);
    for (int i = 0; i<vertexNum; i++) {
        if( edge[position][i] == 1 ){
            return i;
        }
    }
    return -1;
}
int Graph::getNextNevVertex(dataType data ,dataType frontData){
    int position = locate(data);
    int frontPosition = locate(frontData);
    for (int i = frontPosition+1 ; i<vertexNum; i++) {
        if(edge[position][i] == 1){
            return i;
        }
    }
    return  -1;
}

void Graph::breadthFirstSearch(dataType data){
    cout<<"DFS:\n";
    Cqueue queue;
    int position = locate(data);
    int queueHeadPosition = -1;
    if(position == -1){
        cout<<"the vettex is not exist\n";
        return;
    }
    vertex[position].isAccess = true;
    queue.inQueue(position);//  入队列
    
    cout<<position<<endl;
    
    
    while(queue.isEmpty() == false){
        queueHeadPosition = queue.outQueue();//获得队列的头元素
         cout<<vertex[queueHeadPosition].data<<"\t";
        for (
             int i = getFirstVertex(vertex[queueHeadPosition].data);//获得队列头元素的第一个邻接点
             i>=0;
             i = getNextNevVertex(vertex[queueHeadPosition].data, vertex[i].data)//获得从i之后下一个邻接点
             ) {
            if(vertex[i].isAccess == false){
                queue.inQueue(i);
                vertex[i].isAccess = true;
//                cout<<vertex[i].data<<"\t";
            }
        }
    }
    
    
    
    cout<<endl;
}
